Backward Induction

444 Lecture 16

Brian Weatherson

2024-03-14

Trees

Time

  • The tables we discussed last week represent games where each player moves once, and those moves are simultaneous.
  • But few games are like that.
  • We need a way to represent games that take time.

Trees

  • We do that with trees.
  • A tree represents all the ways that a game that takes place over time could go.

Nodes

  • Trees have nodes.
  • Some nodes are terminal nodes; they represent that the game has ended.
  • Each terminal node has a payout for each of the players.
  • At any other node, either a player moves, or Nature ‘moves’.
  • One of the non-terminal nodes is special: it is the node where the game starts.

Branches

  • Each non-terminal node has branches, leading to other nodes.
  • A move at a node is always a choice of branches.

Example from Bonanno
  • There are two players, 1 and 2.
  • Each player moves once.
  • First 1 moves, then 2 moves, then the game ends.

Example from Bonanno
  • Some books use a special notation for the initial node, such as having an open circle rather than a closed circle.
  • Bonanno doesn’t, but it’s clear in context what the initial node is.

Example from Bonanno
  • As he goes on to note, this isn’t really a tree yet.
  • It describes the physical outcomes of the game at each terminal node, but not the payoffs.

Example from Bonanno

There is a natural function from outcomes to payoffs - more money equals more utility - but it is not a compulsory interpretation.

Future Additions

  • Moves by Nature
  • Moves under uncertainty

Backward Induction

Class of Games We’re Discussing

  • Two-player
  • Turn-taking
  • Finite
  • No hidden facts
  • No randomness
  • We’ll start with zero-sum games, though drop this later.

Five

  • There are two players, who we’ll call A and B.
  • First A moves, then B, then finally A moves again.
  • Each move involves announcing a number, 1 or 2.
  • A wins if after the three moves, the numbers announced sum to 5.
  • B wins otherwise.

Five

Question: How should you play this game?

Game Tree for Five

\(W\) means that A wins, and \(L\) means that B wins.

Solving These Games

  • Work backwards.
  • First, find points where a player has a choice between two terminal nodes.
  • Assume that they will make the higher value for them choice.
  • Mark that choice, e.g., by doubling the line (as the textbook does).
  • If there are ties, mark both of the lines. (This gets more complicated once we leave zero-sum games.)

Solving These Games

  • Assign the value they choose to the choice node.
  • So just the game assigns values to terminal nodes, we’ll now assign value to choice nodes.
  • In Five, we’ll assign the value \(W\) to the bottom right node.

Five (after one step)

Five (after first level)

Next Steps Back

  • Now we do the same thing for B.
  • We act as if B is choosing between terminal nodes.
  • It is as if A doesn’t have a choice - they will just make the choice that is best for them (i.e., worst for B).
  • So B knows what the outcome of each choice will be.

Five (After Two Rounds)

Five (After Two Rounds)

  • So we act as if getting to the left hand node means B wins, and getting to the right hand node means A wins.
  • And now we just have to make the choice for the initial node, using this fact.

Five (Full Graph)

Five - Full Analysis

  • The equilibrium state of the game is that A wins.
  • A plays 2 first.
  • Then B can play anything they line.
  • But whatever they do, A will win, by playing the opposite number.

Backwards Induction

  • This process is called backwards induction.
  • We start at the possible ends of the game.
  • At each step, we assume that each player makes the best decision they can, on the assumption that later players will do the same thing.

Ties

Backwards Induction in Positive Sum Games

Three player game tree

This is three player, but crucially, it is not zero sum.

Three player game tree
  • In the bottom right, Player 3 doesn’t care which choice is made.
  • So we can’t infer what Player 3 will do.

Three player game tree
  • But the other players do care what Player 3 will do.
  • So we can’t just ignore this choice.

Three player game tree
  • The solution is to build two trees, one for each of Player 3’s choices.

Solution One
  • First, assume 3 plays g.
  • Then 2 would play f at node y.
  • So 1 will actually play a.

Solution Two
  • Now, assume 3 plays h.
  • Then 2 would play e at node y.
  • So 1 will actually play b triggering this play.

Multiple Solutions

  • This is a game with multiple backwards induction solutions.
  • The solutions don’t just differ in what Player 3, who faces the tie, plays.
  • They differ in the very first move!

Multiple Solutions

  • This is the totally general case; most solution concepts are like this.
  • But it’s a pain to deal with.
  • And eventually we can solve the game.